FPGAs may be used to implement large systems that include million of gates and megabits of embedded memory. Of the tasks required in creating and optimizing a design, placement of components on the FPGAs and routing connection between components on the FPGA utilizing available resources can be the most challenging and time consuming. In order to satisfy placement and routing specifications, several iterations are often required to determine how components are to be placed on the target device and which routing resources to allocate to connect the components. The complexity of large systems often requires the use of EDA tools to create and optimize their design onto physical target devices. Automated placement and routing algorithms in EDA tools perform the time consuming task of placement and routing of components onto physical devices.
In the past, routability optimizations, where the length of wires used to connect components in a system, were typically performed before placement of the system. Attempts to perform routability optimizations during the early stages of system design required a fair amount of estimations as to the position of components on the target device. In instances where the estimations are inaccurate, the routability optimizations would be ineffective.
Thus, what is needed is an efficient method and apparatus for performing post-placement routability optimization.